package realQuestion.tri89;

import java.util.Arrays;

public class Main2 {



    int num = 0;
    public int countRoutes2(int[] locations, int start, int finish, int fuel) {
        //从开始城市进行搜索
        dfs(locations, start, finish, fuel);
        return num;
    }
    public void dfs(int[] locations, int start, int finish, int fuel){
        //到达目的地且油量>=0时，路径总数+1
        if(start == finish && fuel>=0){
            num = num+1>1000000007?(num+1)%1000000007:num+1;
        }
        //搜索可到达的下一个城市
        for(int i = 0;i<locations.length;i++){
            //到达下一个城市还剩的油量
            int k = fuel-Math.abs(locations[start] - locations[i]);
            //如果下一个城市和就是当前城市或者油量不足，则不去，直接查询下一个城市
            if(i == start || k<0){
                continue;
            }
            //搜索下一个可达城市
            dfs(locations, i, finish, k);
        }
    }

    public static void main(String[] args) {
        Main2 main2 = new Main2();
        int[] routes={2,3,6,8,4};
        int i = main2.countRoutes2(routes, 1, 3, 5);
        System.out.println(i);
    }


}
